0152. 乘积最大子数组【中等】
1. 📝 题目描述
给你一个整数数组 nums，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
子数组 是数组中连续的 非空 元素序列。
测试用例的答案是一个 32-位 整数。
示例 1：
txt
输入: nums = [2,3,-2,4]
输出: 6
解释:子数组 [2,3] 有最大乘积 6。1
2
3
2
3
示例 2：
txt
输入: nums = [-2,0,-1]
输出: 0
解释:结果不能为 2, 因为 [-2,-1] 不是子数组。1
2
3
2
3
提示：
1 <= nums.length <= 2 * 10^4-10 <= nums[i] <= 10nums的任何子数组的乘积都 保证 是一个 32-位 整数
2. 🎯 s.1 - 动态规划
c
int maxProduct(int* nums, int numsSize) {
int maxProd = nums[0], curMax = nums[0], curMin = nums[0];
for (int i = 1; i < numsSize; i++) {
if (nums[i] < 0) {
int tmp = curMax;
curMax = curMin;
curMin = tmp;
}
curMax = nums[i] > curMax * nums[i] ? nums[i] : curMax * nums[i];
curMin = nums[i] < curMin * nums[i] ? nums[i] : curMin * nums[i];
if (curMax > maxProd) maxProd = curMax;
}
return maxProd;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
js
/**
* @param {number[]} nums
* @return {number}
*/
var maxProduct = function (nums) {
let maxProd = nums[0],
curMax = nums[0],
curMin = nums[0]
for (let i = 1; i < nums.length; i++) {
if (nums[i] < 0) [curMax, curMin] = [curMin, curMax]
curMax = Math.max(nums[i], curMax * nums[i])
curMin = Math.min(nums[i], curMin * nums[i])
maxProd = Math.max(maxProd, curMax)
}
return maxProd
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
py
class Solution:
def maxProduct(self, nums: List[int]) -> int:
max_prod = cur_max = cur_min = nums[0]
for i in range(1, len(nums)):
if nums[i] < 0:
cur_max, cur_min = cur_min, cur_max
cur_max = max(nums[i], cur_max * nums[i])
cur_min = min(nums[i], cur_min * nums[i])
max_prod = max(max_prod, cur_max)
return max_prod1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
- 时间复杂度：
- 空间复杂度：
算法思路：
- 维护当前位置结尾的最大乘积
curMax和最小乘积curMin - 因为负数乘以负数会变成正数，所以需要同时跟踪最小值
- 当当前元素为负数时，交换
curMax和curMin，然后正常更新